package com.LeeCode;

import java.util.Arrays;

/**
 * 使结果不超过阈值的最小除数
 */

public class Code1283 {
    public static void main(String[] args) {
        int[] nums = {1, 2, 5, 9};
        int threshold = 6;
        System.out.println(new Code1283().smallestDivisor(nums, threshold));
    }

    public int smallestDivisor(int[] nums, int threshold) {
        int left = 0, right = Arrays.stream(nums).max().getAsInt();
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (check(nums, threshold, mid)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }

    private boolean check(int[] nums, int threshold, int divisor) {
        int sum = 0;
        for (int i = nums.length - 1; i >= 0; i--) {
            sum += (nums[i] + divisor - 1) / divisor;
            if (sum > threshold) {
                return false;
            }
        }
        return true;
    }
}
